package sort.leetcode;

/**
 * 归并排序解决数组逆序对问题
 * @author yuisama
 * @date 2022/05/29 09:41
 **/
public class Num51_reversePairs {
    public int reversePairs(int[] nums) {
        return reversePairsInternal(nums,0,nums.length - 1);
    }

    /**
     * 在nums[l..r]上进行归并排序，返回排序后的逆序对的个数
     * @param nums
     * @param l
     * @param r
     * @return
     */
    private int reversePairsInternal(int[] nums, int l, int r) {
        // 数组为空或者只有一个元素
        if (l >= r) {
            return 0;
        }
        int mid = l + (r - l) / 2;
        // 先求出第一个子数组的逆序对个数
        int leftCount = reversePairsInternal(nums,l,mid);
        // 再求出第二个子数组的逆序对个数
        int rightCount = reversePairsInternal(nums,mid + 1,r);
        if (nums[mid] > nums[mid + 1]) {
            // 左右数组有序后，这两个数组之间还存在逆序，merge过程再求出此时合并过程中的逆序对个数
            return leftCount + rightCount + merge(nums,l,mid,r);
        }
        // nums[mid] < nums[mid + 1]整个数组已经有序，不可能再有逆序对了！
        return leftCount + rightCount;
    }

    /**
     * 合并两个有序的子数组nums[l..mid] nums[mid + 1..r]返回合并后逆序对个数
     * @param nums
     * @param l
     * @param mid
     * @param r
     * @return
     */
    private int merge(int[] nums, int l, int mid, int r) {
        // 合并的时候产生的逆序对的个数
        int count = 0;
        int aux[] = new int[r - l + 1];
        for (int i = l; i <= r; i++) {
            aux[i - l] = nums[i];
        }
        int i = l,j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 第一个数组已经处理完毕，直接拼接第二个数组，此时没有逆序对
                nums[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 第二个数组已经处理完毕，直接拼接第一个数组，此时没有逆序对
                nums[k] = aux[i - l];
                i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 拼接第一个数组，此时没有逆序
                nums[k] = aux[i - l];
                i++;
            }else {
                // 此时第一个数组元素 > 第二个数组元素，从i开始到mid结束的所有元素相较于arr[j]都是逆序对
                // 逆序对的个数恰好为mid - i + 1
                count += mid - i + 1;
                nums[k] = aux[j - l];
                j ++;
            }
        }
        return count;
    }
}